/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 044.c
 * egypt number test 1: 1 = SUM(1/n), n is natural number, m is amount of n
 ***********************************************************************************************/

#include <stdio.h>
#include <string.h>

/*
 * in fact, this is not a egypt number test
 * egypt number method may generate much less answers
 * so I call it egypt number test is just for likeness
 */

#define AMOUNT 8
#define SCALE 100 //use 1/1 ~ 1/100 to compose

int used[SCALE]; //used[i] is for number i+1
int egypt[AMOUNT];

int GCD(int m, int n)
{
    int temp = 0;
    if (m < n)
    {
        temp = m;
        m = n;
        n = temp;
    }
    while (n != 0)
    {
        temp = m%n;
        m = n;
        n = temp;
    }
    return(m);
}

void print(int* egypt)
{
    int i;
    for (i = 0; i < AMOUNT; i++)
        printf("%2d/%2d", 1, egypt[i]);
    printf("\n");
}

/*
 * m/n is current value of sum
 * pos is cursor of egypt[] 
 */
int formEgyptNumbers(int m, int n, int pos)
{
    int flag = 0;
    int i;
    int pre_used;
    if (pos == 0) pre_used = 1;
    else pre_used = egypt[pos-1];
    for (i = pre_used; i < SCALE; i++)
    {
        // if i is too large(1/i is too small), it won't fill 1 in limited length
        // this pruning is very useful, bcz it ignores a long tail of range of i
        if ((m*i + (AMOUNT-pos)*n) < n*i)
            break;
        if (used[i-1] != 1) // prevent from using same number to compose
        {
            if ((pos == AMOUNT-1) && (m*i+n == n*i))
            {
                egypt[pos] = i;
                //print(egypt);
                flag++;
                break;
            }
            else if ((pos < AMOUNT-1) && (m*i+n < n*i))
            {
                egypt[pos] = i;
                used[i-1] = 1;
                int a = m*i+n, b = n*i;
                int c = GCD(a, b);
                a /= c;
                b /= c;
                flag += formEgyptNumbers(a, b, pos+1);
                used[i-1] = 0;
            }
        }
    }
    return(flag);
}

int main()
{
	memset(egypt, 0, sizeof(int)*AMOUNT);
	memset(used, 0, sizeof(int)*SCALE);

	int count = 0;
	count = formEgyptNumbers(0, 1, 0);
	printf("Total %d egypt-number groups can form 1\n", count);
}

